/*
 * @lc app=leetcode.cn id=416 lang=typescript
 *
 * [416] 分割等和子集
 */

// @lc code=start
function canPartition(nums: number[]): boolean {
  let sum = nums.reduce((prev, curr) => prev + curr);
  // 不能均分
  if (sum % 2 !== 0) return false;
  // f[i]表示为能否凑成值为i
  const f: boolean[] = new Array(sum + 1).fill(false);
  // 初始化
  f[0] = true;
  sum = 0;
  for (let num of nums) {
    sum += num;
    for (let i = sum; i >= num; i--) {
      f[i] ||= f[i - num];
    }
  }

  return f[sum / 2];
}
// @lc code=end
